<head>
    <meta charset="UTF-8">
<title>算法训练 Professor Monotonic's Network</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div>【问题描述】</div>
<div>无聊的教授最近在做一项关于比较网络的实验。一个比较网络由若干个含两个输入端和两个输出端的比较器组成。如下图，一个比较器将会比较它的两个输入端的值i1和i2，把它们防止在输出端o1和o2上使得o1&lt;=o2。</div>
<div style="text-align: center;"><img src="http://lx.lanqiao.cn/RequireFile.do?fid=dyrJyBtG" width="338" height="105" alt="" /></div>
<div>一个比较网络有n个输入端a1,a2,..,an和n个输出端b1,b2,..,bn。对于每个比较器，它的输入端要么直接连在比较网络的输入端上，要么连在另一个个比较器的输出端上。这样的关系组成的有向图是无环的。下图给出了一个拥有4个输入端、4个输出端、5个比较器的比较网络。</div>
<div style="text-align: center;"><img src="http://lx.lanqiao.cn/RequireFile.do?fid=j5H5aarf" width="697" height="216" alt="" /></div>
<div>在比较网络运行时，值从输入端输入，然后比较器开始工作。当然，一个比较器仅当它的所有输入值已经被算出来后才能开始工作。假设一个比较器需要1单位时间来工作。那么，上面的例子中的比较网络需要3单位时间来计算输出值。图中的comp-1和comp-2是并行工作的，comp-3和comp-4也是，comp-5只有等comp-3和comp-4完成后才能工作。</div>
<div>无聊的教授现在需要帮助确定那些比较网络是排序网络，并且它们需要多长时间来计算输出值。一个排序网络是一个比较网络，并且无论输入如何，它的输出都单调增。上面的例子也是一个比较网络。因为对于每一种可能的输入，输出值都存在关系b1&lt;=b2&lt;=b3&lt;=b4。</div>
<div>【输入格式】</div>
<div>第一行两个整数n,k，分别表示输入值的个数和比较器的个数。</div>
<div>它们满足1&lt;=n&lt;=12，0&lt;=k&lt;=150。</div>
<div>之后<span style="color: rgb(255, 0, 0);"><b>从左到右</b></span>依次给出每个比较器的信息</div>
<div>之后每行两个整数x,y表示第i个比较器将ax,ay做了比较，把其中较小的数放回ax,较大的数放回ay。</div>
<div>【输出格式】</div>
<div>第一行输出YES或NO表示该比较网络是否是排序网络</div>
<div>第二行输出一个整数表示该比较网络的运行时间。</div>
<div>【样例输入】</div>
<div>样例1：</div>
<div>4 5</div>
<div>1 2&nbsp;</div>
<div>3 4</div>
<div>1 3</div>
<div>2 4</div>
<div>2 3</div>
<div>样例2：</div>
<div>8 0</div>
<div>样例3：</div>
<div>3 3</div>
<div>1 2</div>
<div>2 3</div>
<div>1 2</div>
<div>【样例输出】</div>
<div>样例1：</div>
<div>YES</div>
<div>3</div>
<div>样例2：</div>
<div>NO</div>
<div>0</div>
<div>样例3：</div>
<div>YES</div>
<div>3</div>
<div>【样例解释】</div>
<div>样例1即图片上所给的比较网络。</div>